home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / LowUnionFind.cpp < prev    next >
C/C++ Source or Header  |  1999-07-13  |  1KB  |  83 lines
  1. #include "LowUnionFind.h"
  2.  
  3.  
  4. LowUnionFind::LowUnionFind( long inNumVerticies ) {
  5.     int i;
  6.     
  7.     mNumVerticies = inNumVerticies;
  8.     mAdj = new XLongList[ mNumVerticies ];
  9.     mLargest = &mAdj[ 0 ];
  10.     for ( i = 0; i < mNumVerticies; i++ )
  11.         mAdj[ i ].Add( i );
  12. }
  13.  
  14.  
  15.  
  16. LowUnionFind::~LowUnionFind() {
  17.  
  18.     delete []mAdj;
  19. }
  20.  
  21.  
  22.  
  23. void LowUnionFind::AddEdge( long inA, long inB ) {
  24.     
  25.     mAdj[ inA ].Add( inB );
  26.     mAdj[ inB ].Add( inA );
  27.     
  28.     if ( mLargest -> Count() < mAdj[ inA ].Count() )
  29.         mLargest = &mAdj[ inA ];
  30.     else if ( mLargest -> Count() < mAdj[ inB ].Count() )
  31.         mLargest = &mAdj[ inB ];
  32. }
  33.  
  34.  
  35. void LowUnionFind::RemoveVertex( long inA ) {
  36.     long i, n, max = 0;
  37.     XLongList* largest = &mAdj[ 0 ];
  38.         
  39.     for ( i = 0; i < mNumVerticies; i++ ) {
  40.         mAdj[ i ].Remove( inA );
  41.         n = mAdj[ i ].Count();
  42.         if ( n > max ) {
  43.             largest = &mAdj[ i ];
  44.             max = n;
  45.         }
  46.     }
  47.     
  48.     mLargest = largest;
  49. }
  50.  
  51.  
  52.  
  53.  
  54. /*
  55.  
  56. XLongList* LowUnionFind::FindLargestPile() {
  57.     SubTree* tree = (SubTree*) mSubTrees.GetHead();
  58.     long max = tree -> Count(), n;
  59.     SubTree* largest = tree;
  60.     
  61.     tree = (SubTree*) tree -> GetNext();
  62.     
  63.     // For each connected sub graph
  64.     while ( tree ) {
  65.  
  66.         n = tree -> Count();
  67.         if ( n > max ) {
  68.             largest = tree;
  69.             max = n;
  70.         }
  71.  
  72.         tree = (SubTree*) tree -> GetNext();
  73.     }
  74.     
  75.  
  76.     return largest;
  77. }
  78.  
  79.  
  80.  
  81. */
  82.  
  83.